package demo1;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    /**
     * 层序遍历
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();// 要返回的
        Queue<TreeNode> queue = new LinkedList<>();// 队列
        if (root == null) {
            return ret;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }

    /**
     * 求两个结点的公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode LeftTree = lowestCommonAncestor1(root.left, p, q);
        TreeNode RightTree = lowestCommonAncestor1(root.right, p, q);
        if (LeftTree != null && RightTree != null) {
            return root;
        }
        if (LeftTree != null && RightTree == null) {
            return LeftTree;
        }
        if (LeftTree == null && RightTree != null) {
            return RightTree;
        }
        return null;
    }


    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root, p, stackP);
        getPath(root, q, stackQ);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size > 0 && !stackP.isEmpty()) {
                stackP.pop();
                size--;
            }
        }
        if (sizeP < sizeQ) {
            int size = sizeQ - sizeP;
            while (size > 0 && !stackQ.isEmpty()) {
                stackQ.pop();
                size--;
            }
        }

        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek().equals(stackQ.peek())) {
                return stackP.peek();
            } else {
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }

    //root到node的路径结点存储到栈中
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        // 前序遍历,入栈结点
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean f1 = getPath(root.left, node, stack);
        if (f1) {
            //如果root=node了,return
            return true;
        }
        boolean f2 = getPath(root.right, node, stack);
        if (f2) {
            //如果root=node了,return
            return true;
        }
        //如果两个if都没进,说明该结点不是路径,删除
        stack.pop();
        return false;
    }
}